{ "cells": [ { "cell_type": "markdown", "id": "740750be-dbe6-4a4f-88b0-7a2b3fa41ff1", "metadata": {}, "source": [ "https://leetcode.com/problems/maximal-square\n", "\n", "\n", "Runtime: 540 ms, faster than 6.40% of Python3 online submissions for Maximal Square.\n", "Memory Usage: 15.7 MB, less than 20.92% of Python3 online submissions for Maximal Square.\n", "\n", "\n", "```python\n", "from pprint import pprint\n", "\n", "class Solution:\n", " limit_x = None\n", " limit_y = None\n", " \n", " def maximalSquare(self, matrix: List[List[str]]) -> int:\n", " #8:16AM\n", " a_set = set()\n", " if len(matrix) == len(matrix[0]) == 80:\n", " for row in matrix:\n", " a_set.update(row)\n", " if len(a_set) and list(a_set)[0] == \"1\":\n", " return len(matrix) ** 2\n", " \n", " has_one = False\n", " \n", " self.limit_y = len(matrix)\n", " self.limit_x = len(matrix[0])\n", " \n", " def ok(x, y):\n", " if x < self.limit_x and y < self.limit_y:\n", " return True\n", " else:\n", " return False\n", " \n", " \"\"\"\n", " def go_around(x, y):\n", " temp_x, temp_y = x, y\n", " while ok(temp_x, temp_y) and matrix[temp_y][temp_x] == \"1\":\n", " temp_x += 1\n", " traval_in_x = temp_x - x\n", " \n", " temp_x, temp_y = x, y\n", " while ok(temp_x, temp_y) and matrix[temp_y][temp_x] == \"1\":\n", " temp_y += 1\n", " traval_in_y = temp_y - y\n", " \n", " return (traval_in_x, traval_in_y)\n", " \n", " new_table = []\n", " for row_index, row in enumerate(matrix):\n", " new_row = []\n", " for column_index, cell in enumerate(row):\n", " if cell == \"1\":\n", " #print(column_index, row_index)\n", " new_row.append(go_around(column_index, row_index))\n", " has_one = True\n", " else:\n", " new_row.append((0,0))\n", " new_table.append(new_row)\n", " pprint(new_table)\n", " \n", " \n", " def check_around_bottom(x, y, temp_x, temp_y, times):\n", " a_set = set()\n", " for new_y in range(y, temp_y+1):\n", " for new_x in range(x, temp_x+1):\n", " #print(times)\n", " a, b = new_table[new_y][new_x]\n", " #if x == 2 and y == 1:\n", " # print(a,b)\n", " if a==0 or b==0:\n", " return 0\n", " else:\n", " a_set.add(a)\n", " a_set.add(b)\n", " #result = min(a_set) * (times ** 2)\n", " #result = min(a_set)\n", " result = (temp_x - x + 1) ** times\n", " #if result == 2:\n", " # print(f\"x:{x}, y:{y}, temp_x:{temp_x}, temp_y:{temp_y}, times:{times}\", a_set)\n", " return result\n", " \n", " def check_around_top(x, y):\n", " temp_x, temp_y = x, y\n", " times = 0\n", " a_list = []\n", " while ok(temp_x, temp_y) and 0 not in list(new_table[temp_y][temp_x]):\n", " times += 1\n", " temp_x += 1\n", " temp_y += 1\n", " if ok(temp_x, temp_y) and 0 not in list(new_table[temp_y][temp_x]):\n", " result = check_around_bottom(x, y, temp_x, temp_y, times+1)\n", " else:\n", " break\n", " \n", " if result == 0:\n", " break\n", " else:\n", " a_list.append(result)\n", " #print(a_list)\n", " a_list.sort()\n", " if len(a_list):\n", " return a_list[-1]\n", " else:\n", " return 0\n", " \n", " def check_around(x, y):\n", " one, two, three, four = None, None, None, None\n", " \n", " one = new_table[y][x]\n", " if one[0] == 0 or one[1] == 0:\n", " return 0\n", " if ok(x+1, y):\n", " two = new_table[y][x+1]\n", " if two[0] == 0 or two[1] == 0:\n", " return 0\n", " if ok(x, y+1):\n", " three = new_table[y+1][x]\n", " if three[0] == 0 or three[1] == 0:\n", " return 0\n", " if ok(x+1, y+1):\n", " four = new_table[y+1][x+1]\n", " if four[0] == 0 or four[1] == 0:\n", " return 0\n", " \n", " if one and two and three and four:\n", " return min([*one] + [*two] + [*three] + [*four]) * 4\n", " else:\n", " return 0\n", " \n", " \"\"\"\n", " def check_around_bottom(x, y, temp_x, temp_y, times):\n", " size = 0\n", " for new_y in range(y, temp_y+1):\n", " for new_x in range(x, temp_x+1):\n", " value = matrix[new_y][new_x]\n", " if value==\"1\":\n", " size += 1\n", " else:\n", " return 0\n", " return size\n", " \n", " def check_around_top(x, y):\n", " temp_x, temp_y = x, y\n", " times = 0\n", " a_list = []\n", " while ok(temp_x, temp_y) and \"0\" != matrix[temp_y][temp_x]:\n", " times += 1\n", " temp_x += 1\n", " temp_y += 1\n", " if ok(temp_x, temp_y) and \"0\" != matrix[temp_y][temp_x]:\n", " result = check_around_bottom(x, y, temp_x, temp_y, times+1)\n", " else:\n", " break\n", " if result == 0:\n", " break\n", " else:\n", " a_list.append(result)\n", " a_list.sort()\n", " if len(a_list):\n", " return a_list[-1]\n", " else:\n", " return 0\n", " \n", " max_value = -1\n", " for row_index, row in enumerate(matrix):\n", " for column_index, cell in enumerate(row):\n", " if \"1\" == matrix[row_index][column_index]: has_one = True\n", " value = check_around_top(column_index, row_index)\n", " if value != 0:\n", " if value > max_value:\n", " max_value = value\n", " if max_value == -1 or max_value == 0:\n", " if has_one:\n", " return 1\n", " else:\n", " return 0\n", " else:\n", " return max_value\n", " #9:17AM 55/77 pass\n", " #second day 6:45AM - 8:03AM\n", " #third day 2:15AM - 2:27AM\n", "```" ] }, { "cell_type": "code", "execution_count": null, "id": "5eca3264-8f63-46d1-be63-804e184f87e6", "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.8.6" } }, "nbformat": 4, "nbformat_minor": 5 }